package 中等.动态规划.背包;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums 和一个整数 target 。
 * <p>
 * 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
 * <p>
 * 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
 * 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/target-sum
 */
public class 目标和_494 {

    public static void main(String[] args) {

        int[] nums = {1, 1, 1, 1, 1};
        System.out.println(findTargetSumWays(nums, 3));

    }

    /**
     * x-y=target
     * x+y=total
     * x=(target+total)/2
     * 0-1背包问题：
     * 在nums中选中某些数字可以等于y背包的组合数量
     * *  0  1
     * 1  1  1
     * 1  1  选：剩余容量为0，不选：
     * 1  1
     * 1  1
     * 1  1
     */
    public static int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        if (sum - target < 0 || (target + sum) % 2 == 1) {  //x和y不能有小数
            return 0;
        }
        int backPack = (target + sum) / 2 - target; //背包大小，优先选择比较小的那个背包
        // dp[i][j]表示当背包容量为j时，选择前i件物品时，最多的组合数量
        int[][] dp = new int[nums.length + 1][backPack + 1];
        // 当物品数量为0时，并且背包容量为0时，最多的组合数量为1，什么都不选,否则，当物品数量为0时，背包容量大于0，没有满足条件的组合
        //dp[0][0]=1
        //dp[0][1~backPack]=0
        dp[0][0] = 1;
        // 注意：当背包容量为0时，组合数量不一定为1，因为物品中也有0，可以增加2种选择
        for (int i = 1; i <= nums.length; i++) {
            int num = nums[i - 1];
            for (int curBackPack = 0; curBackPack <= backPack; curBackPack++) {
                if (num > curBackPack) {  //当前物品大于背包总容量，不能选当前物品
                    dp[i][curBackPack] = dp[i - 1][curBackPack];
                } else {  //选：那么剩余容量为curBackPack - num，选了第i件物品，那么curBackPack - num的容量不能选i
                    dp[i][curBackPack] = dp[i - 1][curBackPack - num] + dp[i - 1][curBackPack];
                }
            }
        }
        return dp[nums.length][backPack];
    }

}
